문제 사이트
https://school.programmers.co.kr/learn/courses/30/lessons/17680
문제 간단 요약
입력
- 캐시 크기(
cacheSize)- 기억할 수 있는 도시의 수
- 0 <=
cacheSize<= 30
- 도시이름 배열(
cities)- 입력되는 도시 이름 순서
- 도시이름은 영문자로 되어있음
- 도시이름은 대소문자를 구분하지 않음 (ex. Jeju == jeJU)
- 1 <=
len(cities)<= 100000
출력
- 입력된 도시이름 배열을 순서대로 처리할 때 걸리는 총 실행시간을 구하는 문제
조건
- 캐시 교체 알고리즘:
LRU(Least Recently Used)- 가장 최근에 사용한 것이 캐시에 남아있는 알고리즘
(가장 사용한지 오래된 것을 캐시에서 빼는 방식)
- 가장 최근에 사용한 것이 캐시에 남아있는 알고리즘
cache hit일 경우 실행시간: 1- 캐시 안에 도시 이름이 있는 경우
cache miss일 경우 실행시간: 5- 캐시 안에 도시 이름이 없는 경우
풀이
고려할 점
- 대소문자가 섞여있는 도시 이름
lower(): 소문자로 이름 통일
- 도시 이름을 기억하는 캐시가 필요함
deque: FIFOcache miss가 났을 때,popleft()로 가장 오래된 도시 이름을 빼기에 적합함
cache라는 큐에 cacheSize이하의 도시 이름들을 저장한다.
그리고 처리할 도시 이름이 cache에 있는지 없는지에 따라 cache hit와 cache miss로 나누어 처리한다.
cache hit의 경우
원래 캐시 내에 존재하던 도시 이름을 제거하고(remove)
제일 뒤(가장 최신)에 이름을 넣어준다. (append)
그리고 총 실행시간에 +1을 해준다.
cache miss의 경우
캐시에 도시 이름을 넣어주고(append)
만약 캐시가 넘쳤다면, 가장 오래된 이름을 제거해준다. (popleft)
그리고 총 실행시간에 +5를 해준다.
❋ 실제 캐시 시스템은 공간을 확보한 후 데이터를 저장하지만, 구현을 단순화하고 cacheSize == 0인 경우까지 자연스럽게 처리하기 위해 먼저 삽입한 뒤 캐시 크기를 초과하면 가장 오래된 데이터를 제거하도록 구현함
from collections import deque
def solution(cacheSize, cities):
total_processing_time = 0
cache = deque([])
for city in cities:
city = city.lower()
# cache hit
if city in cache:
cache.remove(city)
cache.append(city)
total_processing_time += 1
# cache miss
else:
cache.append(city)
if len(cache) > cacheSize:
cache.popleft()
total_processing_time += 5
return total_processing_time
AI’s comment
좋은 점
1 ) cache miss 시 축출(가장 오래된 항목 제거)을 popleft로 O(1) 에 처리함
2 ) 삽입 후 초과 시 제거하는 구조라 cacheSize == 0 엣지 케이스를 별도 분기 없이 흡수함
아쉬운 점
1 ) (핵심 로직·성능) cache hit 경로의 in과 remove가 앞에서부터 찾아 각각 O(n) 임 (핵심 병목)
다만 이 문제는 cacheSize <= 30이라 n이 작아 실제 성능 차이는 미미하고, 점근적으로 더 나은 방식이 있다는 관점의 지적임
if city in cache: # O(n)
cache.remove(city) # O(n)2 ) (가독성·유지보수) cache hit=1, cache miss=5가 코드에 그대로 박힌 매직 넘버임. 이름 붙은 상수로 빼면 의미가 드러나고 조건이 바뀌어도 한 곳만 고치면 됨
HIT, MISS = 1, 5
...
total_processing_time += HIT # cache hit
total_processing_time += MISS # cache miss3 ) (견고성) if len(cache) > cacheSize는 반복마다 하나만 추가하므로 정확하지만, “한 번에 하나만 넣는다”는 암묵적 전제에 기댐 — 방어적으로는 while이 더 안전함 (이 문제 범위에선 문제 없음)
4 ) (사소) deque([])의 []는 불필요함 — deque()만으로 빈 덱이 생성됨
cache = deque([]) # 수정 전
cache = deque() # 수정 후다른 풀이
1 ) collections의 OrderedDict
deque 대신 해시 기반 자료구조를 써서 조회·삭제·최근사용 갱신을 모두 O(1)로 처리
from collections import OrderedDict
def solution(cacheSize, cities):
if cacheSize == 0: # cacheSize==0을 앞에서 분기 처리 (원본은 삽입 후 초과 제거로 대응)
return len(cities) * 5
cache = OrderedDict() # 원본의 deque → OrderedDict
total = 0
for city in cities:
city = city.lower()
if city in cache: # 원본의 O(n) in → 해시 조회 O(1)
cache.move_to_end(city) # 원본의 remove + append → 이 한 줄, O(1)
total += 1
else:
if len(cache) == cacheSize:
cache.popitem(last=False) # 원본의 popleft에 대응, 가장 오래된 값 제거 O(1)
cache[city] = True # 값은 안 쓰므로 True로 표시만
total += 5
return total2 ) 일반 dict의 삽입 순서 유지를 이용한 코드
OrderedDict 없이도 dict가 삽입 순서를 보존하는 점(Python 3.7부터 언어 명세로 보장)을 활용
def solution(cacheSize, cities):
if cacheSize == 0:
return len(cities) * 5
cache = {} # OrderedDict → 일반 dict
total = 0
for city in cities:
city = city.lower()
if city in cache:
del cache[city] # move_to_end 대신 삭제 후
cache[city] = True # 다시 넣어 맨 뒤(최신)로 보냄
total += 1
else:
if len(cache) == cacheSize:
oldest = next(iter(cache)) # 첫 키 = 가장 오래된 것
del cache[oldest]
cache[city] = True
total += 5
return total